// 给定两个以字符串形式表示的非负整数num1和num2，要求返回num1和num2的乘积，它们的乘积也表示为字符串形式
// 注意： num1和num2的长度小于110, num1和num2只包含数字0-9，num1和num2均不以0开头，除非是数字0本身
// 不能使用任何标准库的大叔类型，或者直接将输入转为整数来处理

// 思路：数组模拟大数相乘，两个数相乘，相乘的结果长度可能为len1 + len2 - 1 或则len1 + len2
// 用len1 + len2长的结果存储各位相乘的结果
// 时间复杂度：O(m * n)，m是num1的长度，n是num2的长度
// 空间复杂度：O(m + n)，nums数组的大小

function multiply(str1, str2) {
    if (str1 === '0' || str2 === '0') {
        return '0'
    }
    let arr1 = str1.split('')
    let arr2 = str2.split('')
    let arr = new Array(arr1.length + arr2.length).fill(0)
    for (let i = arr1.length - 1; i >= 0; i--) {
        for (let j = arr2.length - 1; j >= 0; j--) {
            arr[i + j + 1] += arr1[i] * arr2[j]
        }        
    }
    for (let i = arr.length - 1; i > 0; i--) {
        arr[i - 1] += Math.floor( arr[i] / 10)
        arr[i] = arr[i] % 10
    }
    let res = ''
    for (let i = arr[0] === 0 ? 1 : 0; i < arr.length; i++) {
        res += arr[i]        
    }
    return res
}

let num1 = "123", num2 = "456"
console.log(multiply(num1, num2));